package sort;

public class MaoPaoSort {

	public static void main(String[] args) {

		int[] arr = new int[]{1, 4, 6, 9, 5, 2, 3, 90, 23, 11};
		//bubbleSort1(arr,arr.length);
		//bubbleSort2(arr, arr.length);
		//bubbleSort3(arr,arr.length);
	}
	public static void bubbleSort2(int[] a, int n) {
		long start = System.currentTimeMillis();
		int j, k = n;
		boolean flag = true;//发生了交换就为true, 没发生就为false，第一次判断时必须标志位true。
		while (flag) {
			flag = false;//每次开始排序前，都设置flag为未排序过
			for (j = 1; j < k; j++) {
				if (a[j - 1] > a[j]) {//前面的数字大于后面的数字就交换
					//交换a[j-1]和a[j]
					int temp;
					temp = a[j - 1];
					a[j - 1] = a[j];
					a[j] = temp;

					//表示交换过数据;
					flag = true;
				}
			}
			k--;//减小一次排序的尾边界
		}//end while
		long end = System.currentTimeMillis();
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println("优化后：" + (end - start));
	}//end


	public static void bubbleSort1(int[] a, int n) {
		long start = System.currentTimeMillis();
		int i, j;

		for (i = 0; i < n; i++) {//表示n次排序过程。
			for (j = 1; j < n - i; j++) {
				if (a[j - 1] > a[j]) {//前面的数字大于后面的数字就交换
					//交换a[j-1]和a[j]
					int temp;
					temp = a[j - 1];
					a[j - 1] = a[j];
					a[j] = temp;
				}
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("优化前：" + (end - start));
	}// end


	public static void bubbleSort3(int[] a, int n) {
		long start = System.currentTimeMillis();
		int j, k;
		int flag = n;//flag来记录最后交换的位置，也就是排序的尾边界

		while (flag > 0) {//排序未结束标志
			k = flag; //k 来记录遍历的尾边界
			flag = 0;

			for (j = 1; j < k; j++) {
				if (a[j - 1] > a[j]) {//前面的数字大于后面的数字就交换
//交换a[j-1]和a[j]
					int temp;
					temp = a[j - 1];
					a[j - 1] = a[j];
					a[j] = temp;

//表示交换过数据;
					flag = j;//记录最新的尾边界.
				}
			}
		}
		long end = System.currentTimeMillis();
		System.out.println("优化后2：" + (end - start));
	}
}
